/*二次离线莫队
* 1.二次离线莫队
    二次离线莫队是一共需要离线两次来做，
    在做莫队时，我们每次都会对一段区间去查询一个数，然后我们都会去对两个端点进行移动，
    然后在新的维护区间中去求我们的询问

* 2.做法:
    当我们每次更新完维护区间之后，对于区间的询问很难算，
    所以我们需要在每次更新完维护区间之后，再把当前询问单独拎出来再重新离线求当前询问的值

    想使用莫队算法来求，那么每次我们都需要从上一个询问区间 [l,r] 的信息快速得到当前询问区间 [L,R] 的信息。
    以右端点 r 为例，当 r 右移后，我们需要将 w[r+1] 加入到维护区间中，那么我们就需要考虑将 w[r+1] 加入到维护区间中后，维护区间的信息该怎么去维护。
    当我们将 w[r+1] 加入后, 显然配对的数量只会增加，至于增加的数量，就是 [l,r] 中和 w[r+1] 配对的数的个数，这一步可以用前缀和来求

    设 Si 表示 w1∼wi 中有多少个数和 w[r+1] 配对, 
    此时对于 [l,r] 中和 w[r+1] 配对的数的个数就是 S[r]−S[l−1]
    设 f[i] 表示 w[1]∼w[i] 中与 w[i+1] 配对的数个数, 且S[r]显然就是f[i]
    设g[x]表示前i个数中有多少个数与x配对，f[i]=g[w[i+1]]

    因此，对于前i-1个数的g[x],我们枚举所有y[i],令[y[i] ^ w[i]]+1,最终得到g[x]
    再用g[x]计算f[i],用g[x]辅助递推f[i]

    在考虑S[l-1],就是 w[1]∼w[l-1] 中与 w[r+1] 配对的数个数
    按照从前往后的顺序计算所有询问,直到我们算完所有前缀是 l−1 的询问后，就处理完了所有的询问

    到此我们就能将前一个询问到当前询问的增量 S[r]−S[l−1] 求出来，
    但是这并不是当前询问的答案，
    如果我们想求某一个询问的结果的话，还需要将前面求出来的所有增量累加成前缀和才是最终答案

*/

#define DEBUG
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
const int N=1e5+10;
using ll=long long;
inline int read()
{
	int x=0;char c=getchar();
	while (c<'0'||c>'9') c=getchar();
	while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+c-48,c=getchar();
	return x;
}
inline void write(ll x)
{
	if (x>=10) write(x/10);
	putchar(x%10+48);
}//快读快输

inline int get(int x);

struct Query{
    int id, l, r;
    ll ans; //由于每个询问的答案可能分成多个部分分别处理，需要先将部分答案单独存下来
    bool operator< (const Query& q1) const
    {
        int l1=get(l), l2=get(q1.l);
        return l1!=l2?l1<l2:r<q1.r;
    }
}query[N];

struct Range
{
    int id, l, r, t; //编号、左端点、右端点、类型（1 表示加上，-1 表示减去）
};
//range[i] 表示询问 w[l] ~ w[r] 中每个数和 w[1] ~ w[i] 共有多少个配对
vector<Range> range[N]; //移动区间端点的操作 存储每个询问中需要二次离线解决的问题

int w[N];
ll ans[N];
int n, m, k, len;
int f[N], g[N];
//f[i] 表示 w[1] ~ w[i] 中与 w[i + 1] 配对的数的个数
//g[x] 表示前 i 个数中与 x 配对的数的个数

inline int get(int x)
{
    return x/len;
}

inline int Count1(int x) //计算B(x)中有多少位1
{
    int res=0;
    for(int i=0; i<14; i++) res+=x>>i&1;
    return res;
}

signed main()
{
    #ifdef DEBUG
        freopen("./in.txt","r",stdin);
        freopen("./out.txt","w",stdout);
    #endif

    n=read(); m=read(); k=read();
    for(int i=1; i<=n; i++) w[i]=read();

    vector<int> nums; //存储所有二进制表示中有 k 个 1 的数
    for(int i=0; i<1<<14; i++) //枚举所有数
        if(Count1(i)==k) //如果当前有k个1
            nums.push_back(i);

    //预处理f[]
    for(int i=1; i<=n; i++)
    {
        for(auto j:nums) ++g[w[i]^j]; //w[i]^j配对一次
        f[i]=g[w[i+1]]; //w[i+1]配对的次数
    }

    for(int i=1; i<=m; i++)
    {
        int l=read(), r=read();
        query[i]={i, l, r}; 

    }
    
    len=sqrt(n);
    sort(query+1, query+1+m);

    for(int i=1, L=1, R=0; i<=m; i++)
    {
        int l=query[i].l, r=query[i].r;

        //R右移至r，则[R+1, r]中的所有-S[L-1]需要二次离线处理
        if(R<r) range[L-1].push_back({i, R+1, r, -1}); 
        while(R<r) query[i].ans+=f[R++]; //R右移至r，加入w[R+1]， ans+(S[R]-S[L-1])

        //R右移至r，则[r+1, R]中的所有+S[L-1]需要二次离线处理
        if(r<R) range[L-1].push_back({i, r+1, R, 1});
        while(r<R) query[i].ans-=f[--R]; //R左移至r，删去w[R]， ans-(S[R-1]-S[L-1])

        //L右移至l，则[L, l-1]中的所有-S[R]需要二次离线处理
        if(L<l) range[R].push_back({i, L, l-1, -1});
        while(L<l) query[i].ans+=f[L-1]+!k, L++; //L右移至l，删去w[L]， ans-(S[R]-S[L])

        //L左移至l，则[L, l-1]中的所有+S[R]需要二次离线处理
        if(l<L) range[R].push_back({i, l, L-1, 1});
        while(l<L) query[i].ans-=f[L-2]+!k, L--; //L左移至l，删去w[L-1] ans+=(S[R]-S[L-1])
    }

    memset(g, 0, sizeof g);

    //二次离线
    for(int i=1; i<=n; i++)
    {
        for(auto j:nums) ++g[w[i]^j];  //递推出前 i 个数的 g[]
        for(auto &rg : range[i]) //处理所有和 1 ~ i 求配对的询问
        {
            int id = rg.id, l = rg.l, r = rg.r, t = rg.t;
            for(int x = l; x <= r; x++) 
                query[id].ans += 1ll*g[w[x]] * t; //将求出的结果加入对应询问的答案中
        }
    }

    for(int i=2; i<=m; i++)
        query[i].ans+=query[i-1].ans;

    for(int i=1; i<=m; i++)
        ans[query[i].id]=query[i].ans;

    for(int i=1; i<=m; i++)
        write(ans[i]), puts("");

    return 0;
}